/*
 * ICS 211
 * Fall 2011
 * Homework 5
 * @author Ryne Okimoto
 * 
 * LinkedList class.  Creates a linked list and performs
 * operations on that list.
 */

package dlldynamicset;

import java.io.IOException;
import java.util.ArrayList;
import java.util.Scanner;
import project1driver.SetData;
import readfile.ReadStringFile;

// Old code implemented java.lang.iterable<E>

public class DLLDynamicSet <E, K extends Comparable<K>>
{	
	// Data for DLLDynamicSet
	private DLLNode<E, K> head;
	private DLLNode<E, K> tail;
	private int size;
	
	private static long startTime;
	private static long duration;
	private static long minTime;
	private static long maxTime;
	private static long aveTime;
	private static long time_sum;
	private SetData dll_data;
	private ArrayList<DLLNode<E, K>> dll_elements;
	
	/**
	*	Default constructor
	*	Initializes an empty list.
	*/
	public DLLDynamicSet()
	{
		head = null;
		tail = null;
		size = 0;
		dll_data = new SetData("DLL");
		dll_elements = new ArrayList<DLLNode<E, K>>(0);
	}
	
	private void resetTime()
	{
		startTime = 0;
		duration = 0;
		minTime = 0;
		maxTime = 0;
		aveTime = 0;
		time_sum = 0;
	}
	
	public SetData runtest(Object[] fileData, int[] randomIndices)
	{
		resetTime();
		
		// Insert data
		for(int i = 0; i < fileData.length; i++)
		{
			startTime = System.nanoTime();
			this.insertData((E) fileData[i], (K) fileData[i]);
			duration = System.nanoTime() - startTime;
			
			if(minTime == 0)
			{
				minTime = duration;
			}
			else if(duration < minTime)
			{
				minTime = duration;
			}
			
			if(maxTime == 0)
			{
				maxTime = duration;
			}
			else if(duration > maxTime)
			{
				maxTime = duration;
			}
			
			time_sum = time_sum + duration;
		}
		
		aveTime = time_sum / fileData.length;
		
		dll_data.insert_results[0] = minTime;
		dll_data.insert_results[1] = aveTime;
		dll_data.insert_results[2] = maxTime;
		
		// Search data
		resetTime();
		
		for(int i = 0; i < 10; i++)
		{
			startTime = System.nanoTime();
			dll_elements.add(search((K) fileData[randomIndices[i]]));
			duration = System.nanoTime() - startTime;
			
			if(minTime == 0)
			{
				minTime = duration;
			}
			else if(duration < minTime)
			{
				minTime = duration;
			}
			
			if(maxTime == 0)
			{
				maxTime = duration;
			}
			else if(duration > maxTime)
			{
				maxTime = duration;
			}
			
			time_sum = time_sum + duration;
		}
		
		aveTime = time_sum / fileData.length;
		
		dll_data.search_results[0] = minTime;
		dll_data.search_results[1] = aveTime;
		dll_data.search_results[2] = maxTime;
		
		// Predecessor data
		resetTime();
		
		for(int i = 0; i < 10; i++)
		{
			startTime = System.nanoTime();
			predecessor(dll_elements.get(i));
			duration = System.nanoTime() - startTime;
			
			if(minTime == 0)
			{
				minTime = duration;
			}
			else if(duration < minTime)
			{
				minTime = duration;
			}
			
			if(maxTime == 0)
			{
				maxTime = duration;
			}
			else if(duration > maxTime)
			{
				maxTime = duration;
			}
			
			time_sum = time_sum + duration;
		}
		
		aveTime = time_sum / fileData.length;
		
		dll_data.pred_results[0] = minTime;
		dll_data.pred_results[1] = aveTime;
		dll_data.pred_results[2] = maxTime;
		
		// Successor data
		resetTime();
		
		for(int i = 0; i < 10; i++)
		{
			startTime = System.nanoTime();
			successor(dll_elements.get(i));
			duration = System.nanoTime() - startTime;
			
			if(minTime == 0)
			{
				minTime = duration;
			}
			else if(duration < minTime)
			{
				minTime = duration;
			}
			
			if(maxTime == 0)
			{
				maxTime = duration;
			}
			else if(duration > maxTime)
			{
				maxTime = duration;
			}
			
			time_sum = time_sum + duration;
		}
		
		aveTime = time_sum / fileData.length;
		
		dll_data.succ_results[0] = minTime;
		dll_data.succ_results[1] = aveTime;
		dll_data.succ_results[2] = maxTime;
		
		// Maximum data
		resetTime();
		startTime = System.nanoTime();
		maximum();
		duration = System.nanoTime() - startTime;
		
		dll_data.timeOfMax = duration;
		
		// Minimum data
		resetTime();
		startTime = System.nanoTime();
		minimum();
		duration = System.nanoTime() - startTime;
		
		dll_data.timeOfMin = duration;
		
		
		return dll_data;
	}
	
	public void insertData(E nodeData, K nodeKey)
	{
		this.insert(new DLLNode<E, K>(nodeData, nodeKey));
	}
	
	/**
	*	Method to insert an element into the list
	*	Pre: The list is sorted
	*	Post: The list is sorted
	*
	*/
	public void insert(DLLNode<E, K> nodeToAdd)
	{
		// Empty list
		if(head == null && tail == null)
		{
			head = nodeToAdd;
			tail = nodeToAdd;
		}
		// Non-empty list
		else
		{
			DLLNode<E, K> tempNode = head;
			while(tempNode.getNext() != null && nodeToAdd.compareTo(tempNode) > 0)
			{
				tempNode = tempNode.getNext();
			}
			
			// One element
			if(tempNode == head && tempNode == tail)
			{
				// Before head
				if(nodeToAdd.compareTo(tempNode) < 0)
				{
					tempNode.setPrevious(nodeToAdd);
					nodeToAdd.setNext(tempNode);
					head = nodeToAdd;
					tail = tempNode;
				}
				// After head
				else if(nodeToAdd.compareTo(tempNode) > 0)
				{
					tempNode.setNext(nodeToAdd);
					nodeToAdd.setPrevious(tempNode);
					tail = nodeToAdd;
				}
			}
			// More than one element
			else
			{
				// Add at the beginning
				if(tempNode == head)
				{
					// Before head
					if(nodeToAdd.compareTo(tempNode) < 0)
					{
						tempNode.setPrevious(nodeToAdd);
						nodeToAdd.setNext(tempNode);
						head = nodeToAdd;
					}
					// After head
					else if(nodeToAdd.compareTo(tempNode) > 0)
					{
						tempNode.getNext().setPrevious(nodeToAdd);
						nodeToAdd.setNext(tempNode.getNext());
						
						tempNode.setNext(nodeToAdd);
						nodeToAdd.setPrevious(tempNode);
					}
					
				}
				// Add at the end
				else if(tempNode == tail)
				{
					// before tail
					if(nodeToAdd.compareTo(tempNode) < 0)
					{
						tempNode.getPrevious().setNext(nodeToAdd);
						nodeToAdd.setPrevious(tempNode.getPrevious());
						
						tempNode.setPrevious(nodeToAdd);
						nodeToAdd.setNext(tempNode);
					}
					// after tail
					else if(nodeToAdd.compareTo(tempNode) > 0)
					{
						tempNode.setNext(nodeToAdd);
						nodeToAdd.setPrevious(tempNode);
						tail = nodeToAdd;
					}
				}
				// Add in between
				else
				{
					if(nodeToAdd.compareTo(tempNode) > 0)
					{
						tempNode.getNext().setPrevious(nodeToAdd);
						nodeToAdd.setNext(tempNode.getNext());
						
						tempNode.setNext(nodeToAdd);
						nodeToAdd.setPrevious(tempNode);
					}
					else if(nodeToAdd.compareTo(tempNode) < 0)
					{
						tempNode.getPrevious().setNext(nodeToAdd);
						nodeToAdd.setPrevious(tempNode.getPrevious());
						
						tempNode.setPrevious(nodeToAdd);
						nodeToAdd.setNext(tempNode);
					}
				}
			}
		}
		/*
		// Add to empty list
		if(head == null)
		{
			head = nodeToAdd;
			tail = nodeToAdd;
		}
		else
		{
			DLLNode<E, K> tempNode = head;
			while(tempNode.getNext() != null && nodeToAdd.compareTo(tempNode) > 0)
			{
				tempNode = tempNode.getNext();
			}
			
			// List contains one element
			if(tempNode == head)
			{
				// Add before head
				if(nodeToAdd.compareTo(tempNode) < 0)
				{
					tempNode.setPrevious(nodeToAdd);
					nodeToAdd.setNext(tempNode);
					head = nodeToAdd;
					tail = tempNode;
				}
				// Add after head
				else if(nodeToAdd.compareTo(tempNode) > 0)
				{
					tempNode.setNext(nodeToAdd);
					nodeToAdd.setPrevious(tempNode);
					tail = nodeToAdd;
				}
			}
			
			// List contains more than 1 element
			else
			{
				// Add before
				if(nodeToAdd.compareTo(tempNode) < 0)
				{
					// Connect added node
					nodeToAdd.setNext(tempNode);
					nodeToAdd.setPrevious(tempNode.getPrevious());
					
					// Change references for tempNode
					tempNode.getPrevious().setNext(nodeToAdd);
					tempNode.setPrevious(nodeToAdd);
				}
				// Add after
				else if(nodeToAdd.compareTo(tempNode) > 0)
				{
					if(tempNode.getNext() != null)
					{
						// Connect added node
						nodeToAdd.setPrevious(tempNode);
						nodeToAdd.setNext(tempNode.getNext());
						
						// Change references for tempNode
						tempNode.getNext().setPrevious(nodeToAdd);
						tempNode.setNext(nodeToAdd);
					}
					// Add at the tail
					else
					{
						
					}
					
					if(tempNode == tail)
					{
						tail = nodeToAdd;
					}
				}
			}
		} 
		*/
		
		size++;
	}
	
	/**
	 * deleteKey
	 * 
	 * Description: public wrapper method to delete a key
	 * 
	 * @param searchKey
	 * @return
	 */
	public boolean deleteKey(K searchKey)
	{
		DLLNode<E, K> result = search(searchKey);
		boolean keyDeleted = false;
		
		if(result != null)
		{
			delete(result);
			keyDeleted = true;
		}
		
		return keyDeleted;
	}
	
	/**
	*	Method to delete an element from the list if it exists
	*	Pre: The list is sorted
	*	Post: The list is sorted
	*/
	public void delete(DLLNode<E, K> nodeToDelete)
	{
		DLLNode<E, K> searchResult = null;
		
		if(head != null)
		{
			if(nodeToDelete.compareTo(head) == 0)
			{
				// Delete from list with one item
				if(head == tail)
				{
					head = null;
					tail = null;
				}
				// Delete from head of list
				else
				{
					head = head.getNext();
					head.setPrevious(null);
				}
			}
			// Delete from tail of list
			else if(nodeToDelete.compareTo(tail) == 0)
			{
				tail = tail.getPrevious();
				tail.setNext(null);
			}
			// Delete from within list
			else
			{
				searchResult = search(nodeToDelete.getKey());
				if(searchResult != null)
				{
					searchResult.getPrevious().setNext(searchResult.getNext());
					searchResult.getNext().setPrevious(searchResult.getPrevious());
				}
			}	
		}
		size--;
	}
	
	public int size()
	{
		return size;
	}
	
	/**
	 * searchForKey
	 * 
	 * Description: Public wrapper method to search for a key and return it if found
	 * @param searchKey
	 * @return
	 */
	public K searchForKey(K searchKey)
	{
		DLLNode<E, K> result = search(searchKey);
		
		if(result != null)
		{
			return result.getKey();
		}
		else
		{
			return null;
		}
	}
	
	public DLLNode<E, K> search(K key)
	{
		DLLNode<E, K> searchResult = head;
		
		while((searchResult != null) && (searchResult.getKey().compareTo(key) != 0))
		{
			searchResult = searchResult.getNext();
		}
		
		return searchResult;
	}
	
	public DLLNode<E, K> minimum()
	{
		return head;
	}
	
	public DLLNode<E, K> maximum()
	{
		return tail;
	}
	
	/**
	 * findSuccessor
	 * 
	 * Description: public wrapper method to search for the successor of a key
	 * 
	 * @param searchKey
	 * @return
	 */
	
	public K findSuccessor(K searchKey)
	{
		DLLNode<E, K> result = search(searchKey);
		
		if(result != null)
		{
			result = successor(result);
		}
		
		if(result != null)
		{
			return result.getKey();
		}
		return null;
	}
	
	public DLLNode<E, K> successor(DLLNode<E, K> node)
	{
		return node.getNext();
	}
	
	/**
	 * findPredecessor
	 * 
	 * Description: Public wrapper method to find a predecessor
	 * @param searchKey
	 * @return
	 */
	public K findPredecessor(K searchKey)
	{
		DLLNode<E, K> result = search(searchKey);
		
		if(result != null)
		{
			result = predecessor(result);
		}
		
		if(result != null)
		{
			return result.getKey();
		}
		return null;
	}
	
	public DLLNode<E, K> predecessor(DLLNode<E, K> node)
	{
		return node.getPrevious();
	}
	
	public String toString()
	{
		DLLNode<E, K> printedNode = head;
		String printedString = null;
		
		while(printedNode != null)
		{
			if(printedString == null)
			{
				printedString = printedNode.toString() + "\n";
			}
			else
			{
				printedString = printedString.concat(printedNode.toString() + "\n");
			}
			
			printedNode = printedNode.getNext();
		}
		
		return printedString;
	}
	
	
	/**
	 * Unit tester for the class
	 * @param none
	 */
	public static void main(String[] args) 
	{
		
		char command = '0';
		DLLDynamicSet<String, String> testList = new DLLDynamicSet<String, String>();
		Scanner readInput = new Scanner(System.in);
		String key = null;
		String data = null;
		DLLNode<String, String> searchResult = null;
		String keyAndData;
		
		readInput.useDelimiter("\n");
		
		System.out.println("Unit test for DLLDynamicSet and DLLNode\n");
		
		while(command != 'q')
		{
			System.out.print(
					"\n\n\n******   Command Menu   ******\n\n" +
					"1) Insert item\n" +
					"2) Delete item\n" +
					"3) Get size of list\n" +
					"4) Get minimum\n" +
					"5) Get maximum\n" +
					"6) Find successor\n" +
					"7) Find predecessor\n" +
					"8) Print keys\n" +
					"9) Read data from file\n" +
					"q) Quit\n\n" +
					": "
					);
			try{
				command = readInput.next().toCharArray()[0];
			}catch(IndexOutOfBoundsException i)
			{
				//System.out.println("Please enter a selection.");
			}
			
			switch(command)
			{
			case '1':
				data = null;
				key = null;
				
				System.out.print("\n\n******   Test insert   ******" + "\n" +
						"Enter node data: "
						);
				data = readInput.next();
				
				System.out.print("Enter node key: ");
				key = readInput.next();
				
				testList.insert(new DLLNode<String, String>(data, key, null, null));
				
				break;
			case '2':
				searchResult = null;
				data = null;
				key = null;
				
				System.out.print("\n\n******   Test delete   ******" + "\n" +
						"Enter key: "
						);
				key = readInput.next();
				
				searchResult = testList.search(key);
				if(searchResult != null)
				{
					testList.delete(searchResult);
					System.out.println("Key deleted.");
				}
				else
				{
					System.out.println("Key not found.");
				}
				
				break;
			case '3':
				System.out.print("\n\n******   Size of list ******\n" +
						"Number of elements: " + testList.size()
						);
				break;
			case '4':
				System.out.print("\n\n******   Get minimum   ******\n" +
						"Minimum key: " + testList.minimum()
						);
				break;
			case '5':
				System.out.print("\n\n******   Get maximum   ******\n" +
						"Maximum key: " + testList.maximum()
						);
				break;
			case '6':
				searchResult = null;
				data = null;
				key = null;
				
				System.out.print("\n\n******   Find successor   ******\n" +
						"Enter key: "
						);
				
				key = readInput.next();
				searchResult = testList.search(key);
				if(searchResult != null)
				{
					System.out.println("Successor: " + testList.successor(searchResult));
				}
				else
				{
					System.out.println("Key not found");
				}
				
				break;
			case '7': 
				searchResult = null;
				data = null;
				key = null;
				
				System.out.print("\n\n******   Find predecessor   ******\n" +
						"Enter key: "
						);
				key = readInput.next();
				searchResult = testList.search(key);
				if(searchResult != null)
				{
					System.out.println("Predecessor: " + testList.predecessor(searchResult));
				}
				else
				{
					System.out.println("Key not found");
				}
				break;
			case '8':
				System.out.println(testList);
				break;
			case '9':
				System.out.print("\n\n******   Read data from file   ******" + "\n" +
						"Enter a file name: "
						);
				ReadStringFile fileToRead = new ReadStringFile(readInput.next());
				try {
					while(fileToRead.hasLine())
					{
						keyAndData = fileToRead.readLine();
						testList.insert(new DLLNode<String, String>(keyAndData, keyAndData));
					}
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
				break;
			case 'q':
				System.out.println("Exiting program...");
				break;
			default:
				System.out.println("Please choose a valid option.");
			}
			
		}
		
		
	}
}
